package com.leetcode.partition3;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/17 8:47
 */
public class LC226翻转二叉树 {

    public static TreeNode invertTree(TreeNode root) {
        return recursion(root);
    }

    private static TreeNode bfs(TreeNode root) {
        if (root == null) return null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.pollFirst();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
        return root;
    }

    private static TreeNode iteration(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if (cur.right != null) s.push(cur.right);
            if (cur.left != null) s.push(cur.left);
        }
        return root;
    }

    private static TreeNode recursion(TreeNode root) {
        if (root == null) return null;
        //交换左右子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        recursion(root.left);
        recursion(root.right);
        return root;
    }
}
